package list

//递归的思想解决： 先找出前半段链表，这部分链表不包含val。 紧接着去掉val的部分，将剩下部分依次处理。
//若前半段不为nil。则返回前部分头指针，并将前部分尾指针指向后面的链表的头指针
//若前半段为nil，直接返回后半段的值。
func removeElements(head *ListNode, val int) *ListNode {
	if head == nil { //递归结束的条件，这里要有。否则会出现[1,1,1] val= 1 会有死循环
		return nil
	}
	node := head
	var pre *ListNode
	for ; node != nil && node.Val != val; node = node.Next {
		if pre == nil {
			head = node
		}
		pre = node
	}
	for ; node != nil && node.Val == val; node = node.Next {
	}
	nextHead := removeElements(node, val)
	if pre == nil {
		return nextHead
	}
	pre.Next = nextHead
	return head
}
